package com.whitedust.top20;

import com.whitedust.structure.TreeNode;

/**
 * @author A
 * @since 2025/11/3 15:27
 */

public class Top19 {
    //最近公共祖先
    //在判定时，需要左右子树的结果，所以必须采取后序遍历
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return postOrder(root, p, q);
    }

    //详细逻辑写法
    public TreeNode postOrder(TreeNode root, TreeNode p, TreeNode q) {
        //找到子节点或者是找到目标节点即可返回,终止递归
        if (root == null || root == p || root == q) return root;
        TreeNode left = postOrder(root.left, p, q);
        TreeNode right = postOrder(root.right, p, q);
        if (left != null && right != null) return root;
        if (left != null && right == null) return left;
        if (right != null && left == null) return right;
        return null;
    }

    //简化写法
    public TreeNode postOrder1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = postOrder(root.left, p, q);
        TreeNode right = postOrder(root.right, p, q);
        if (left != null && right != null) return root;
        if (left != null) return left;
        return right;
    }
}
